Shortest Path
Q1.
Let G=(V,E) be a directed, weighed graph with weight function w:E\rightarrow \mathbb{R}. For some function f:V\rightarrow \mathbb{R}, for each edge (u,v) \in E, define w'(u,v) as w(u,v)+f(u)-f(v). Which one of the options completes the following sentence so that it is TRUE? "The shortest paths in G under w are shortest paths under w' too,_________".Q2.
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?Q3.
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 isQ5.
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not changeQ6.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q7.
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W. W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix} The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.Q8.
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, byQ9.
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:Q10.
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing